package com.bee.剑指offer;

import java.util.ArrayList;

public class 二叉树中和为某一值的路径2 {

    private static ArrayList<Integer> result = new ArrayList<>();

    private static boolean flag = false;

    private static int count = 0;

    public boolean hasPathSum1 (TreeNode root, int sum) {
        if(root == null || flag) {
            return flag;
        }
//        sum -= root.val;
        count += root.val;
        result.add(root.val);
        if(root.left == null && root.right == null && count == sum) {
            flag = true;
            return true;
        }
        hasPathSum1(root.left,sum);
        hasPathSum1(root.right,sum);
        count -= result.get(result.size() - 1);
        result.remove(result.size() - 1);
        return flag;
    }

    public boolean hasPathSum2 (TreeNode root, int sum) {
        if(root == null || flag) {
            return flag;
        }
        sum -= root.val;
        result.add(root.val);
        if(root.left == null && root.right == null && sum == 0) {
            flag = true;
            return true;
        }
        hasPathSum2(root.left,sum);
        hasPathSum2(root.right,sum);
        result.remove(result.size() - 1);
        return flag;
    }


    public static void main(String[] args) {

    }
}
